This invention is a circuit for rotating a digital image by multiples of ninety degrees by transferring the original image from memory, a raster input scanner or the like, into a buffer using a first addressing and shifting process, and using a second addressing and shifting process to read out from the buffer back into the memory, raster output scanner or the like, so that the image is rotated, all bits of each word being transferred to and from the buffer in parallel.
The representation of a visual image by a two-dimensional array is well known. Such an array is typically composed of rows and columns of picture elements, termed pixels. Such a pixel may represent the color or density of a spot of the total image, and can be one or a number of binary bits or words, or analog voltages. A principal advantage of this representation is that it allows image processing systems to handle pixels one at a time, rather than to try to handle the whole picture all at once. For systems which transmit, display or print images from pixels, the usual one-at-a-time pixel order is a scheme called "raster ordering". In raster ordering, a pixel array is divided into scan lines corresponding to its columns (or to its rows), and pixels are sequentially accessed in the same direction along each scan line, starting with the first scan line along one edge of the pixel array and continuing with the next adjacent scan line until all the scan lines have had their pixels accessed. To increase the performance of image processing systems, each scanline of a pixel array is often partitioned into fixed-size subsets of adjacent pixels, called "words", the word size being a constant over the entire pixel array. In such systems an entire word is transferred or stored at a time. Memory subsystems for storing an entire word of pixels in parallel this way are called "word organized memories". Storing a pixel array in raster order into a linear word organized memory results in the words of each scanline occupying consecutive word addresses and the scanlines of the array abutting end to end.
It is a common requirement in digital document processors that a page that is scanned into the system in one orientation be printed out in another. An example would be a scanned-in image which was stored in the system in the "landscape" mode, but must be printed in the "portrait" mode. In this case, it is easier for the operator to rotate the image electronically than to re-scan the image, and is the only way if the original is no longer available. Also, in many systems, the image is displayed to the operator for editing on a display which uses horizontal scan lines and then printed on a printer which uses vertical scan lines. The result is that a printing system needs to be able to create rotated and unrotated images at any stage of processing. However, because of the memory order, the parallel fetch of adjacent pixels along a scanline is easier to accomplish than the parallel fetch of adjacent pixels perpendicular to the scanlines. For example, in a typical memory of sixteen bit words, the first sixteen bit word of an image is loaded into the first bit of the first sixteen memory chips, the second word is loaded into the second bit of the sixteen memory chips, etc. Therefore, if a line comprising bits in the direction of the word length is needed to be output, sixteen bits at a time may be accessed in parallel since each bit is in a different memory chip. However, if the line is perpendicular to the word length, then the individual bits are all in the same chip and can only be accessed serially, which is a very slow process in comparison.
The difficulty of word-parallel access to both the rows and columns of a stored pixel array has presented a considerable challenge to the prior art. Image processing systems have often needed to change the scan direction or image orientation of a pixel array by 90 degrees. Some approaches, like those of U.S. Pat. Nos. 3,976,982, and 4,562,485 use slow one-pixel-at-a-time access. Other approaches store a pixel array into memory and then incur a delay by performing a separate conversion process to change the pixel array into a stored 90 degree rotated version before transmitting, displaying or printing it. Many of these approaches do this by transferring small subsets of the pixel array at a time to a separate rotator, as in U.S. Pat. Nos. 4,052,699; 4,168,488; 4,271,476; 4,593,407; 4,627,020; 4,636,783, and also the system described by Kornfeld in "The Image Prism: A Device for Rotating and Mirroring Bitmap Images", IEEE Computer Graphics and Applications, May 1987. Thus, all of the store-and-convert approaches require at least one additional fetch and store of the entire pixel array after its initial storage in memory.
What is required is a rotation method which needs only one data transfer into the buffer and only one data transfer out of the buffer, and where these two data transfers operate on entire words in parallel.